package NC50_链表中的节点每k个一组翻转;

import java.util.*;


class ListNode {
    int val;
    ListNode next = null;

    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class Solution {
    /**
     *
     * @param head ListNode类
     * @param k int整型
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        if (head == null || head.next == null || k < 2){
            return head;
        }
        
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        int len = length(head);
        // pre是每一小段的头结点，负责衔接；
        //cur用来行走链表，其实相当于已遍历过的尾结点，其下面一个就是即将插入头部的节点;
        //temp用来存储需要删除的以及即将插入头部的节点。
        ListNode pre = dummy, cur = head, temp;
        for (int i = 0; i < len / k; i++){
            for (int j = 1; j < k; j++){
                temp = cur.next;
                cur.next = temp.next;   // 相当于把 temp 删除
                temp.next = pre.next;   // 头插
                pre.next = temp;
            }
            pre = cur;
            cur = cur.next;
        }
        return dummy.next;
    }

    private int length(ListNode head) {
        int len = 0;
        while (head != null){
            len++;
            head = head.next;
        }
        return len;
    }
}